Euclidean space given a set of constraints like "item

Methods for global navigation satellite system fault detection using Euclidean Distance Matrices have been presented recently in the literature. Published methods define a test statistic in terms of eigenvalues of a certain matrix, but the distribution of the test statistic was not known, which presented a barrier to practical implementation. This document was a personal correspondence from Beatty to Derek Knowles. It includes a brief derivation of the distribution of the test statistic and a representative case showing that the theoretical distribution closely matches a simulated empirical distribution.

Numerous methods have been proposed for global navigation satellite system (GNSS) receivers to detect faulty GNSS signals. One such fault detection and exclusion (FDE) method is based on the mathematical concept of Euclidean distance matrices (EDMs). This paper outlines a greedy approach that uses an improved Euclidean distance matrix-based fault detection and exclusion algorithm. The novel greedy EDM FDE method implements a new fault detection test statistic and fault exclusion strategy that drastically simplifies the complexity of the algorithm over previous work. To validate the novel greedy EDM FDE algorithm, we created a simulated dataset using receiver locations from around the globe. The simulated dataset allows us to verify our results on 2,601 different satellite geometries. Additionally, we tested the greedy EDM FDE algorithm using a real-world dataset from seven different android phones. Across both the simulated and real-world datasets, the Python implementation of the greedy EDM FDE algorithm is shown to be computed an order of magnitude more rapidly than a comparable greedy residual FDE method while obtaining similar fault exclusion accuracy. We provide discussion on the comparative time complexities of greedy EDM FDE, greedy residual FDE, and solution separation. We also explain potential modifications to greedy residual FDE that can be added to alter performance characteristics.

The goal of ordinal embedding is to represent items as points in a low-dimensional Euclidean space given a set of constraints like "item i is closer to item j than item k". Ordinal constraints like this often come from human judgments. The classic approach to solving this problem is known as non-metric multidimensional scaling. To account for errors and variation in judgments, we consider the noisy situation in which the given constraints are independently corrupted by reversing the correct constraint with some probability. The ordinal embedding problem has been studied for decades, but most past work pays little attention to the question of whether accurate embedding is possible, apart from empirical studies. This paper shows that under a generative data model it is possible to learn the correct embedding from noisy distance comparisons. In establishing this fundamental result, the paper makes several new contributions.

We study the problem of determining the configuration of $n$ points, referred to as mobile nodes, by utilizing pairwise distances to $m$ fixed points known as anchor nodes. In the standard setting, we have information about the distances between anchors (anchor-anchor) and between anchors and mobile nodes (anchor-mobile), but the distances between mobile nodes (mobile-mobile) are not known. For this setup, the Nystr\"om method is a viable technique for estimating the positions of the mobile nodes. This study focuses on the setting where the anchor-mobile block of the distance matrix contains only partial distance information. First, we establish a relationship between the columns of the anchor-mobile block in the distance matrix and the columns of the corresponding block in the Gram matrix via a graph Laplacian. Exploiting this connection, we introduce a novel sampling model that frames the position estimation problem as low-rank recovery of an inner product matrix, given a subset of its expansion coefficients in a special non-orthogonal basis. This basis and its dual basis--the central elements of our model--are explicitly derived. Our analysis is grounded in a specific centering of the points that is unique to the Nystr\"om method. With this in mind, we extend previous work in Euclidean distance geometry by providing a general dual basis approach for points centered anywhere.

Generating point clouds, e.g., molecular structures, in arbitrary rotations, translations, and enumerations remains a challenging task. Meanwhile, neural networks utilizing symmetry invariant layers have been shown to be able to optimize their training objective in a data-efficient way. In this spirit, we present an architecture which allows to produce valid Euclidean distance matrices, which by construction are already invariant under rotation and translation of the described object. Motivated by the goal to generate molecular structures in Cartesian space, we use this architecture to construct a Wasserstein GAN utilizing a permutation invariant critic network. This makes it possible to generate molecular structures in a one-shot fashion by producing Euclidean distance matrices which have a three-dimensional embedding.

This paper corrects the proof of the Theorem 2 from the Gower's paper \cite[page 5]{Gower:1982}. The correction is needed in order to establish the existence of the kernel function used commonly in the kernel trick e.g. for $k$-means clustering algorithm, on the grounds of distance matrix. The scope of correction is explained in section 2.

The goal of ordinal embedding is to represent items as points in a low-dimensional Euclidean space given a set of constraints like ``item $i$ is closer to item $j$ than item $k$''. Ordinal constraints like this often come from human judgments. The classic approach to solving this problem is known as non-metric multidimensional scaling. To account for errors and variation in judgments, we consider the noisy situation in which the given constraints are independently corrupted by reversing the correct constraint with some probability. The ordinal embedding problem has been studied for decades, but most past work pays little attention to the question of whether accurate embedding is possible, apart from empirical studies. This paper shows that under a generative data model it is possible to learn the correct embedding from noisy distance comparisons. In establishing this fundamental result, the paper makes several new contributions. First, we derive prediction error bounds for embedding from noisy distance comparisons by exploiting the fact that the rank of a distance matrix of points in $\R^d$ is at most $d+2$. These bounds characterize how well a learned embedding predicts new comparative judgments. Second, we show that the underlying embedding can be recovered by solving a simple convex optimization. This result is highly non-trivial since we show that the linear map corresponding to distance comparisons is non-invertible, but there exists a nonlinear map that is invertible. Third, two new algorithms for ordinal embedding are proposed and evaluated in experiments.

Although recovering an Euclidean distance matrix from noisy observations is a common problem in practice, how well this could be done remains largely unknown. To fill in this void, we study a simple distance matrix estimate based upon the so-called regularized kernel estimate. We show that such an estimate can be characterized as simply applying a constant amount of shrinkage to all observed pairwise distances. This fact allows us to establish risk bounds for the estimate implying that the true distances can be estimated consistently in an average sense as the number of objects increases. In addition, such a characterization suggests an efficient algorithm to compute the distance matrix estimator, as an alternative to the usual second order cone programming known not to scale well for large problems. Numerical experiments and an application in visualizing the diversity of Vpu protein sequences from a recent HIV-1 study further demonstrate the practical merits of the proposed method.

We demonstrate that almost all non-parametric dimensionality reduction methods can be expressed by a simple procedure: regularized loss minimization plus singular value truncation. By distinguishing the role of the loss and regularizer in such a process, we recover a factored perspective that reveals some gaps in the current literature. Beyond identifying a useful new loss for manifold unfolding, a key contribution is to derive new convex regularizers that combine distance maximization with rank reduction. These regularizers can be applied to any loss.